/*
 * Copyright (c) 2009-2021 jMonkeyEngine
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are
 * met:
 *
 * * Redistributions of source code must retain the above copyright
 *   notice, this list of conditions and the following disclaimer.
 *
 * * Redistributions in binary form must reproduce the above copyright
 *   notice, this list of conditions and the following disclaimer in the
 *   documentation and/or other materials provided with the distribution.
 *
 * * Neither the name of 'jMonkeyEngine' nor the names of its contributors
 *   may be used to endorse or promote products derived from this software
 *   without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
package com.jme3.scene;

import com.jme3.bounding.BoundingBox;
import com.jme3.bounding.BoundingVolume;
import com.jme3.collision.Collidable;
import com.jme3.collision.CollisionResults;
import com.jme3.export.JmeExporter;
import com.jme3.export.JmeImporter;
import com.jme3.material.Material;
import com.jme3.scene.threadwarden.SceneGraphThreadWarden;
import com.jme3.util.SafeArrayList;
import com.jme3.util.clone.Cloner;
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
import java.util.logging.Level;
import java.util.logging.Logger;

/**
 * <code>Node</code> defines an internal node of a scene graph. The internal
 * node maintains a collection of children and handles merging said children
 * into a single bound to allow for very fast culling of multiple nodes. Node
 * allows for any number of children to be attached.
 *
 * @author Mark Powell
 * @author Gregg Patton
 * @author Joshua Slack
 */
public class Node extends Spatial {
    private static final Logger logger = Logger.getLogger(Node.class.getName());
    /**
     * This node's children.
     */
    protected SafeArrayList<Spatial> children = new SafeArrayList<>(Spatial.class);
    /**
     * If this node is a root, this list will contain the current
     * set of children (and children of children) that require
     * updateLogicalState() to be called as indicated by their
     * requiresUpdate() method.
     */
    private SafeArrayList<Spatial> updateList = null;
    /**
     * False if the update list requires rebuilding.  This is Node.class
     * specific and therefore not included as part of the Spatial update flags.
     * A flag is used instead of nulling the updateList to avoid reallocating
     * a whole list every time the scene graph changes.
     */
    private boolean updateListValid = false;

    /**
     * Instantiate a <code>Node</code> with no name, no parent, and no children.
     */
    public Node() {
        this(null);
    }

    /**
     * Constructor instantiates a new <code>Node</code> with a default empty
     * list for containing children.
     *
     * @param name the name of the scene element
     */
    public Node(String name) {
        super(name);
        // For backwards compatibility, only clear the "requires
        // update" flag if we are not a subclass of Node.
        // This prevents subclass from silently failing to receive
        // updates when they upgrade.
        setRequiresUpdates(Node.class != getClass());
    }

    /**
     * <code>getQuantity</code> returns the number of children this node
     * maintains.
     *
     * @return the number of children this node maintains.
     */
    public int getQuantity() {
        return children.size();
    }

    @Override
    protected void setTransformRefresh() {
        super.setTransformRefresh();
        for (Spatial child : children.getArray()) {
            if ((child.refreshFlags & RF_TRANSFORM) != 0) {
                continue;
            }

            child.setTransformRefresh();
        }
    }

    @Override
    protected void setLightListRefresh() {
        super.setLightListRefresh();
        for (Spatial child : children.getArray()) {
            if ((child.refreshFlags & RF_LIGHTLIST) != 0) {
                continue;
            }

            child.setLightListRefresh();
        }
    }

    @Override
    protected void setMatParamOverrideRefresh() {
        super.setMatParamOverrideRefresh();
        for (Spatial child : children.getArray()) {
            if ((child.refreshFlags & RF_MATPARAM_OVERRIDE) != 0) {
                continue;
            }

            child.setMatParamOverrideRefresh();
        }
    }

    @Override
    protected void updateWorldBound() {
        super.updateWorldBound();
        // for a node, the world bound is a combination of all its children
        // bounds
        BoundingVolume resultBound = null;
        for (Spatial child : children.getArray()) {
            // child bound is assumed to be updated
            assert (child.refreshFlags & RF_BOUND) == 0;
            if (resultBound != null) {
                // merge current world bound with child world bound
                resultBound.mergeLocal(child.getWorldBound());
            } else {
                // set world bound to first non-null child world bound
                if (child.getWorldBound() != null) {
                    resultBound = child.getWorldBound().clone(this.worldBound);
                }
            }
        }
        if (resultBound == null) {
            resultBound = new BoundingBox(getWorldTranslation(), 0f, 0f, 0f);
        }
        this.worldBound = resultBound;
    }

    @Override
    protected void setParent(Node parent) {
        if (this.parent == null && parent != null) {
            // We were a root before and now we aren't... make sure if
            // we had an updateList then we clear it completely to
            // avoid holding the dead array.
            updateList = null;
            updateListValid = false;
        }
        super.setParent(parent);
    }

    private void addUpdateChildren(SafeArrayList<Spatial> results) {
        for (Spatial child : children.getArray()) {
            if (child.requiresUpdates()) {
                results.add(child);
            }
            if (child instanceof Node) {
                ((Node) child).addUpdateChildren(results);
            }
        }
    }

    /**
     *  Called to invalidate the root node's update list.  This is
     *  called whenever a spatial is attached/detached as well as
     *  when a control is added/removed from a Spatial in a way
     *  that would change state.
     */
    void invalidateUpdateList() {
        assert SceneGraphThreadWarden.assertOnCorrectThread(this);
        updateListValid = false;
        if (parent != null) {
            parent.invalidateUpdateList();
        }
    }

    private SafeArrayList<Spatial> getUpdateList() {
        if (updateListValid) {
            return updateList;
        }
        if (updateList == null) {
            updateList = new SafeArrayList<>(Spatial.class);
        } else {
            updateList.clear();
        }

        // Build the list
        addUpdateChildren(updateList);
        updateListValid = true;
        return updateList;
    }

    @Override
    public void updateLogicalState(float tpf) {
        super.updateLogicalState(tpf);

        // Only perform updates on children if we are the
        // root and then only perform updates on children we
        // know to require updates.
        // So if this isn't the root, abort.
        if (parent != null) {
            return;
        }

        for (Spatial s : getUpdateList().getArray()) {
            s.updateLogicalState(tpf);
        }
    }

    @Override
    public void updateGeometricState() {
        if (refreshFlags == 0) {
            // This branch has no geometric state that requires updates.
            return;
        }
        if ((refreshFlags & RF_LIGHTLIST) != 0) {
            updateWorldLightList();
        }
        if ((refreshFlags & RF_TRANSFORM) != 0) {
            // combine with parent transforms- same for all spatial
            // subclasses.
            updateWorldTransforms();
        }
        if ((refreshFlags & RF_MATPARAM_OVERRIDE) != 0) {
            updateMatParamOverrides();
        }

        refreshFlags &= ~RF_CHILD_LIGHTLIST;
        if (!children.isEmpty()) {
            // the important part- make sure child geometric state is refreshed
            // first before updating own world bound. This saves
            // a round-trip later on.
            // NOTE 9/19/09
            // Although it does save a round trip,
            for (Spatial child : children.getArray()) {
                child.updateGeometricState();
            }
        }

        if ((refreshFlags & RF_BOUND) != 0) {
            updateWorldBound();
        }

        assert refreshFlags == 0;
    }

    /**
     * <code>getTriangleCount</code> returns the number of triangles contained
     * in all sub-branches of this node that contain geometry.
     *
     * @return the triangle count of this branch.
     */
    @Override
    public int getTriangleCount() {
        int count = 0;
        if (children != null) {
            for (int i = 0; i < children.size(); i++) {
                count += children.get(i).getTriangleCount();
            }
        }

        return count;
    }

    /**
     * <code>getVertexCount</code> returns the number of vertices contained
     * in all sub-branches of this node that contain geometry.
     *
     * @return the vertex count of this branch.
     */
    @Override
    public int getVertexCount() {
        int count = 0;
        if (children != null) {
            for (int i = 0; i < children.size(); i++) {
                count += children.get(i).getVertexCount();
            }
        }

        return count;
    }

    /**
     * <code>attachChild</code> attaches a child to this node. This node
     * becomes the child's parent. The current number of children maintained is
     * returned.
     * <br>
     * If the child already had a parent it is detached from that former parent.
     *
     * @param child
     *            the child to attach to this node.
     * @return the number of children maintained by this node.
     * @throws IllegalArgumentException if child is null.
     */
    public int attachChild(Spatial child) {
        return attachChildAt(child, children.size());
    }

    /**
     * <code>attachChildAt</code> attaches a child to this node at an index. This node
     * becomes the child's parent. The current number of children maintained is
     * returned.
     * <br>
     * If the child already had a parent it is detached from that former parent.
     *
     * @param child
     *            the child to attach to this node.
     * @param index
     *            the position where the child should be attached
     * @return the number of children maintained by this node.
     * @throws IllegalArgumentException if child is null or this
     */
    public int attachChildAt(Spatial child, int index) {
        assert SceneGraphThreadWarden.assertOnCorrectThread(this);
        if (child == null) {
            throw new IllegalArgumentException("child cannot be null");
        }
        if (child == this) {
            throw new IllegalArgumentException("Cannot add child to itself");
        }
        if (child.getParent() != this) {
            if (child.getParent() != null) {
                child.getParent().detachChild(child);
            }
            child.setParent(this);
            children.add(index, child);
            // XXX: Not entirely correct? Forces bound update up the
            // tree stemming from the attached child. Also forces
            // transform update down the tree-
            child.setTransformRefresh();
            child.setLightListRefresh();
            child.setMatParamOverrideRefresh();
            if (logger.isLoggable(Level.FINE)) {
                logger.log(Level.FINE, "Child ({0}) attached to this node ({1})",
                        new Object[]{child.getName(), getName()});
            }
            invalidateUpdateList();
        }
        return children.size();
    }

    /**
     * <code>detachChild</code> removes a given child from the node's list.
     * This child will no longer be maintained.
     *
     * @param child
     *            the child to remove (not null)
     * @return the index the child was at. -1 if the child was not in the list.
     */
    public int detachChild(Spatial child) {
        if (child == null) {
            throw new IllegalArgumentException("child cannot be null");
        }

        if (child.getParent() == this) {
            int index = children.indexOf(child);
            if (index != -1) {
                detachChildAt(index);
            }
            return index;
        }

        return -1;
    }

    /**
     * <code>detachChild</code> removes a given child from the node's list.
     * This child will no longer be maintained. Only the first child with a
     * matching name is removed.
     *
     * @param childName
     *            the child to remove (not null)
     * @return the index the child was at. -1 if the child was not in the list.
     */
    public int detachChildNamed(String childName) {
        if (childName == null) {
            throw new IllegalArgumentException("childName cannot be null");
        }

        for (int x = 0, max = children.size(); x < max; x++) {
            Spatial child = children.get(x);
            if (childName.equals(child.getName())) {
                detachChildAt(x);
                return x;
            }
        }
        return -1;
    }

    /**
     * <code>detachChildAt</code> removes a child at a given index. That child
     * is returned for saving purposes.
     *
     * @param index
     *            the index of the child to be removed.
     * @return the child at the supplied index.
     */
    public Spatial detachChildAt(int index) {
        assert SceneGraphThreadWarden.assertOnCorrectThread(this);
        Spatial child = children.remove(index);
        if (child != null) {
            child.setParent(null);
            logger.log(Level.FINE, "{0}: Child removed.", this);

            // since a child with a bound was detached;
            // our own bound will probably change.
            setBoundRefresh();

            // our world transform no longer influences the child.
            // XXX: Not necessary? Since child will have transform updated
            // when attached anyway.
            child.setTransformRefresh();
            // lights are also inherited from parent
            child.setLightListRefresh();
            child.setMatParamOverrideRefresh();

            invalidateUpdateList();
        }
        return child;
    }

    /**
     * <code>detachAllChildren</code> removes all children attached to this
     * node.
     */
    public void detachAllChildren() {
        assert SceneGraphThreadWarden.assertOnCorrectThread(this);
        // Note: this could be a bit more efficient if it delegated
        // to a private method that avoided setBoundRefresh(), etc.
        // for every child and instead did one in here at the end.
        for (int i = children.size() - 1; i >= 0; i--) {
            detachChildAt(i);
        }
        logger.log(Level.FINE, "{0}: All children removed.", this);
    }

    /**
     * <code>getChildIndex</code> returns the index of the given spatial
     * in this node's list of children.
     * @param sp
     *          The spatial to look up
     * @return  The index of the spatial in the node's children, or -1
     *          if the spatial is not attached to this node
     */
    public int getChildIndex(Spatial sp) {
        return children.indexOf(sp);
    }

    /**
     * More efficient than e.g. detaching and attaching, as no updates are needed.
     *
     * @param index1 The index of the first child to swap
     * @param index2 The index of the second child to swap
     */
    public void swapChildren(int index1, int index2) {
        assert SceneGraphThreadWarden.assertOnCorrectThread(this);
        Spatial c2 = children.get(index2);
        Spatial c1 = children.remove(index1);
        children.add(index1, c2);
        children.remove(index2);
        children.add(index2, c1);
    }

    /**
     * <code>getChild</code> returns a child at a given index.
     *
     * @param i   the index to retrieve the child from.
     * @return the child at a specified index.
     */
    public Spatial getChild(int i) {
        return children.get(i);
    }

    /**
     * <code>getChild</code> returns the first child found with exactly the
     * given name (case-sensitive). This method does a depth-first recursive
     * search of all descendants of this node, it will return the first spatial
     * found with a matching name.
     *
     * @param name
     *            the name of the child to retrieve. If null, we'll return null.
     * @return the child if found, or null.
     */
    public Spatial getChild(String name) {
        if (name == null) {
            return null;
        }

        for (Spatial child : children.getArray()) {
            if (name.equals(child.getName())) {
                return child;
            } else if (child instanceof Node) {
                Spatial out = ((Node) child).getChild(name);
                if (out != null) {
                    return out;
                }
            }
        }
        return null;
    }

    /**
     * determines if the provided Spatial is contained in the children list of
     * this node.
     *
     * @param spat
     *            the child object to look for.
     * @return true if the object is contained, false otherwise.
     */
    public boolean hasChild(Spatial spat) {
        if (children.contains(spat)) {
            return true;
        }

        for (Spatial child : children.getArray()) {
            if (child instanceof Node && ((Node) child).hasChild(spat)) {
                return true;
            }
        }

        return false;
    }

    /**
     * Returns all children to this node. Note that modifying that given
     * list is not allowed.
     *
     * @return a list containing all children to this node
     */
    public List<Spatial> getChildren() {
        return children;
    }

    @Override
    public void setMaterial(Material mat) {
        assert SceneGraphThreadWarden.assertOnCorrectThread(this);
        for (int i = 0; i < children.size(); i++) {
            children.get(i).setMaterial(mat);
        }
    }

    @Override
    public void setLodLevel(int lod) {
        super.setLodLevel(lod);
        for (Spatial child : children.getArray()) {
            child.setLodLevel(lod);
        }
    }

    @Override
    public int collideWith(Collidable other, CollisionResults results) {
        int total = 0;
        // optimization: try collideWith BoundingVolume to avoid possibly redundant tests on children
        // number 4 in condition is somewhat arbitrary.
        // When there is only one child, the boundingVolume test is redundant at all.
        // The idea is when there are few children,
        // it can be too expensive to test boundingVolume first.
        /*
        I'm removing this change until some issues can be addressed, and I really
        think it needs to be implemented a better way anyway.
        First, it causes issues for anyone doing collideWith() with BoundingVolumes
        and expecting it to trickle down to the children.  For example, children
        with BoundingSphere bounding volumes and collideWith(BoundingSphere).  Doing
        a collision check at the parent level then has to do a BoundingSphere to BoundingBox
        collision which isn't resolved.  (Having to come up with a collision point in that
        case is tricky and the first sign that this is the wrong approach.)
        Second, the rippling changes this caused to 'optimize' collideWith() for this
        special use-case are another sign that this approach was a bit dodgy.  The whole
        idea of calculating a full collision just to see if the two shapes collide at all
        is very wasteful.
        A proper implementation should support a simpler boolean check that doesn't do
        all of that calculation.  For example, if 'other' is also a BoundingVolume (ie: 99.9%
        of all non-Ray cases) then a direct BV to BV intersects() test can be done.  So much
        faster.  And if 'other' _is_ a Ray then the BV.intersects(Ray) call can be done.
        I don't have time to do it right now, but I'll at least un-break a bunch of people's
        code until it can be 'optimized' properly.  Hopefully it's not too late to back out
        the other dodgy ripples this caused.  -pspeed (hindsight-expert ;))
        Note: the code itself is relatively simple to implement, but I don't have time to
        a) test it, and b) see if '> 4' is still a decent check for it.  Could be it's fast
        enough to do all the time for > 1.
        if (children.size() > 4)
        {
          BoundingVolume bv = this.getWorldBound();
          if (bv==null) return 0;

          // collideWith without CollisionResults parameter used to avoid allocation when possible
          if (bv.collideWith(other) == 0) return 0;
        }
        */
        for (Spatial child : children.getArray()) {
            total += child.collideWith(other, results);
        }
        return total;
    }


     /**
     * Returns flat list of Spatials implementing the specified class AND
     * with name matching the specified pattern.
     * <P>
     * Note that we are <i>matching</i> the pattern, therefore the pattern
     * must match the entire pattern (i.e. it behaves as if it is sandwiched
     * between "^" and "$").
     * You can set regex modes, like case insensitivity, by using the (?X)
     * or (?X:Y) constructs.
     * </P> <P>
     * By design, it is always safe to code loops like:<PRE>
     *     for (Spatial spatial : node.descendantMatches(AClass.class, "regex"))
     * </PRE>
     * <P>
     * "Descendants" does not include self, per the definition of the word.
     * To test for descendants AND self, you must do a
     * <code>node.matches(aClass, aRegex)</code> +
     * <code>node.descendantMatches(aClass, aRegex)</code>.
     * <P>
     *
     * @param <T> the type of Spatial returned
     * @param spatialSubclass Subclass which matching Spatials must implement.
     *                        Null causes all Spatials to qualify.
     * @param nameRegex  Regular expression to match Spatial name against.
     *                        Null causes all Names to qualify.
     * @return Non-null, but possibly 0-element, list of matching Spatials
     *                        (also Instances extending Spatials).
     *
     * @see java.util.regex.Pattern
     * @see Spatial#matches(java.lang.Class, java.lang.String)
     */
    @SuppressWarnings("unchecked")
    public <T extends Spatial> List<T> descendantMatches(
            Class<T> spatialSubclass, String nameRegex) {
        List<T> newList = new ArrayList<>();
        if (getQuantity() < 1) {
            return newList;
        }
        for (Spatial child : getChildren()) {
            if (child.matches(spatialSubclass, nameRegex)) {
                newList.add((T) child);
            }
            if (child instanceof Node) {
                newList.addAll(((Node) child).descendantMatches(
                        spatialSubclass, nameRegex));
            }
        }
        return newList;
    }

    /**
     * Convenience wrapper.
     *
     * @param <T> the type of Spatial returned
     * @param spatialSubclass the type of Spatial returned, or null for all
     * spatials
     * @return a new list of pre-existing spatials (may be empty)
     * @see #descendantMatches(java.lang.Class, java.lang.String)
     */
    public <T extends Spatial> List<T> descendantMatches(
            Class<T> spatialSubclass) {
        return descendantMatches(spatialSubclass, null);
    }

    /**
     * Convenience wrapper.
     *
     * @param <T> the type of Spatial returned
     * @param nameRegex regular expression to match Spatial names against, or null for all spatials
     * @return a new list of pre-existing spatials (may be empty)
     * @see #descendantMatches(java.lang.Class, java.lang.String)
     */
    public <T extends Spatial> List<T> descendantMatches(String nameRegex) {
        return descendantMatches(null, nameRegex);
    }

    @Override
    public Node clone(boolean cloneMaterials) {
        Node nodeClone = (Node) super.clone(cloneMaterials);
//        nodeClone.children = new ArrayList<Spatial>();
//        for (Spatial child : children){
//            Spatial childClone = child.clone();
//            childClone.parent = nodeClone;
//            nodeClone.children.add(childClone);
//        }

        // Reset the fields of the clone that should be in a 'new' state.
        nodeClone.updateList = null;
        nodeClone.updateListValid = false; // safe because parent is nulled out in super.clone()
        return nodeClone;
    }

    @Override
    public Spatial deepClone() {
        Node nodeClone = (Node) super.deepClone();

        // Reset the fields of the clone that should be in a 'new' state.
        nodeClone.updateList = null;
        nodeClone.updateListValid = false; // safe because parent is nulled out in super.clone()

        return nodeClone;
    }

    public Spatial oldDeepClone() {
        Node nodeClone = (Node) super.clone();
        nodeClone.children = new SafeArrayList<>(Spatial.class);
        for (Spatial child : children) {
            Spatial childClone = child.deepClone();
            childClone.parent = nodeClone;
            nodeClone.children.add(childClone);
        }
        return nodeClone;
    }

    /**
     *  Called internally by com.jme3.util.clone.Cloner.  Do not call directly.
     */
    @Override
    public void cloneFields(Cloner cloner, Object original) {
        super.cloneFields(cloner, original);

        this.children = cloner.clone(children);

        // Only the outer cloning thing knows whether this should be nulled
        // or not... after all, we might be cloning a root node in which case
        // cloning this list is fine.
        this.updateList = cloner.clone(updateList);
    }

    @Override
    @SuppressWarnings("unchecked")
    public void write(JmeExporter e) throws IOException {
        super.write(e);
        e.getCapsule(this).writeSavableArrayList(new ArrayList(children), "children", null);
    }

    @Override
    @SuppressWarnings("unchecked")
    public void read(JmeImporter importer) throws IOException {
        // XXX: Load children before loading itself!!
        // This prevents empty children list if controls query
        // it in Control.setSpatial().
        children = new SafeArrayList(Spatial.class,
                importer.getCapsule(this).readSavableArrayList("children", null));

        // go through children and set parent to this node
        if (children != null) {
            for (Spatial child : children.getArray()) {
                child.parent = this;
            }
        }
        super.read(importer);
    }

    @Override
    public void setModelBound(BoundingVolume modelBound) {
        assert SceneGraphThreadWarden.assertOnCorrectThread(this);
        if (children != null) {
            for (Spatial child : children.getArray()) {
                child.setModelBound(modelBound != null ? modelBound.clone(null) : null);
            }
        }
    }

    @Override
    public void updateModelBound() {
        assert SceneGraphThreadWarden.assertOnCorrectThread(this);
        if (children != null) {
            for (Spatial child : children.getArray()) {
                child.updateModelBound();
            }
        }
    }

    @Override
    public void depthFirstTraversal(SceneGraphVisitor visitor, DFSMode mode) {
        if (mode == DFSMode.POST_ORDER) {
            for (Spatial child : children.getArray()) {
                child.depthFirstTraversal(visitor, mode);
            }
            visitor.visit(this);
        } else { //pre order
            visitor.visit(this);
            for (Spatial child : children.getArray()) {
                child.depthFirstTraversal(visitor, mode);
            }
        }
    }

    @Override
    protected void breadthFirstTraversal(SceneGraphVisitor visitor, Queue<Spatial> queue) {
        queue.addAll(children);
    }
}
